/**
 * @(#) DeleteDup.java Jan 21, 2010 7:16:08 PM
 * Copyright (C) 2009 GeeYee Inc. 60606, Chicago, IL, USA
 * All right reserved
 */
package stringoperation;

import array.QuickSort;


/**
 * Class <code>DeleteDup</code>
 * 
 * @author Xiaowen dingxwsimon@gmail.com
 * @since Jan 21, 2010 7:16:08 PM
 * 
 */
public class DeleteDup
{
	//running time n^2
	public char[] removeDuplicates(char[] str)
	{
		//tail always point to the duplicate char
		// if (!str)
		// return;
		
		int len = str.length;
		if (len < 2)
			return str;
		//tail maintain the last index of the non-dup char array
		int tail = 1;
		for (int i = 1; i < len; ++i)
		{
			int j;
			for (j = 0; j < tail; ++j)
				if (str[i] == str[j])
					break;
			if (j == tail)
			{
				str[tail] = str[i];
				++tail;
			}
		}
		str[tail] =  '\0';
		return str;
	}

	public char[] removeDuplicates1(char[] str)
	{
		if (str == null)
			return str;
		int len = str.length;
		
		if (len < 2)
			return str;
		int tail = 1;
		for (int i = 0; i < len; ++i)
		{
			int j;
			for (j = 0; j < tail; ++j)
			{
				if (str[i] == str[j])
				{
					int k;
					for (k = j; k < len - 1; k++)
						str[k] = str[k + 1];
					str[k] = '\0';
				}
			}

		}
		return str;
	}
	
	public char[] removeDuplicates2(char[] str)
	{
		int i, j;
		int Length = str.length;
		/* new length of modified array */
		int NewLength = 1;

		for(i=1; i< Length; i++){

		   for(j=0; j< NewLength ; j++)
		   {

		      if(str[i] == str[j])
		      break;
		   }

		   /* if none of the values in index[0..j] of array is not same as array[i],
		      then copy the current value to corresponding new position in array */

		  if (j==NewLength )
		      str[NewLength++] = str[i];
		}
		str[NewLength] = 0;
		return str;
	}

	
	//sort and then using this nlogn, but this violate the natrual order of the array
	public char[] removeDupfromOrder(char[] str)
	{
		int i = 1, j = 0;
		int Length = str.length;
		
		while(i <= Length - 1)
		{
			if(str[i] == str[i-1]) j++;
			else
				str[i - j] = str[i];
			i++;
				
		}
		str[i - j]=  '\0';
		return str;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args)
	{
		// TODO Auto-generated method stub
		
		String string = "";
		
		char[] str =
		{ 'a', 'b', 'd', 'c', 'e', 'c' , 'b', 'd'};
		DeleteDup rd = new DeleteDup();
		//System.out.println(rd.removeDupfromOrder(str));
		System.out.println(rd.removeDuplicates(str));

	}

}
